/**
 * @fileOverview 
 * Defines methods of geo-polygon-utils library.
 * @author Igor Kulkin <igor.kulkin@gmail.com>
 */


/**
 * @namespace Root namespace for geo-polygon-utils library.
 */
var geoPolygonUtils = geoPolygonUtils || {};


(function() {

  var Precision = geoPolygonUtils.geometry.Precision;
  var Vector = geoPolygonUtils.geometry.Vector;
  var Line = geoPolygonUtils.geometry.Line;
  var Segment = geoPolygonUtils.geometry.Segment;

  /** @exports polygonEquals as geoPolygonUtils.polygonEquals */
  var polygonsEqual =
    /**
     * Checks whether two given polygons are eqaul.
     * Note: two polygons are considered to be equal if their sequences
     * of vertices match exactly (modulo given precision), i.e. no cyclic
     * shift of vertices is allowed.
     *
     * @param {Array<Vector>} polygonA
     * @param {Array<Vector>} polygonB
     * @param {Precision|Number} [precision] Precision for comparison. 
     * @returns {Boolean}
     */
    geoPolygonUtils.polygonsEqual = function(polygonA, polygonB, precision) {
      if (polygonA.length != polygonB.length) return false;
      for (var i = 0; i < polygonA.length; ++i) {
        if (!polygonA[i].equals(polygonB[i], precision)) return false;
      }
      return true;
    };


  /** @exports isValidPolygon as geoPolygonUtils.isValidPolygon */
  var isValidPolygon =
    /**
     * Checks whether a given polygon is a valid polygon (i.e. doesn't have self-intersections).
     *
     * @param {Array<Vector>} polygon
     * @returns {Boolean}
     */
    geoPolygonUtils.isValidPolygon = function(polygon) {
      // TODO(kulkin): this function doesn't check for segments overlap, which may be a problem
      //     when all the vertices lie on a single line.
      if (polygon.length >= 3) {
        for (var i = 1; i < polygon.length; ++i) {
          var seg0 = new Segment(polygon[i], polygon[(i + 1) % polygon.length]);
          // Here we iterate over all segments preceding segment #i, which are not neighbours
          // with it (the initial value of j is just a simple trick to avoid checking segment
          // #0 when (i == polygon.length - 1)).
          for (var j = Math.max(0, i + 2 - polygon.length); j + 1 < i; ++j) {
            var seg1 = new Segment(polygon[j], polygon[(j + 1) % polygon.length]);
            var point = seg0.intersectSegment(seg1);
            if (point) {
              return false;
            }
          }
        }
      }
      return true;
    };

  /** @exports simplifyPolygon as geoPolygonUtils.simplifyPolygon */
  var simplifyPolygon =
    /**
     * Simplifies a given polygon by merging consecutive vertices in case they are close
     * enough to each other.
     *
     * @param {Array<Vector>} polygon
     * @param {Precision|Number} [precision] Simplification precision.
     * @returns {Array<Vector>|null} Simplified polygon. 'null' is returned in case the given
     *     polygon can't be simplified.
     */
    geoPolygonUtils.simplifyPolygon = function(polygon, precision) {
      precision = Precision.createForUnit(precision);
      // TODO(kulkin): make this method also temove vertices if they are close to a segment
      //     connecting to neighbor vertices.
      var result = [];
      if (polygon.length == 0) {
        return result;
      }
      result.push(polygon[0]);
      for (var i = 1; i < polygon.length; ++i) {
        var last = result.length - 1;
        if (result[last].distanceToPoint(polygon[i]) < precision.UNIT) {
          result[last] = result[last].plus(polygon[i]).multiply(0.5);
        } else {
          result.push(polygon[i]);
        }
      }

      var last = result.length - 1;
      while (last > 0 && result[0].distanceToPoint(result[last]) < precision.UNIT) {
        result[0] = result[0].plus(result[last]).multiply(0.5);
        last--;
      }
      last++;
      if (last != result.length) {
        result.splice(last, result.length - last);
      }

      if (result.length == polygon.length) {
        return null;
      }
      return result;
    };


  /**
   * Finds difference between two given polar angles.
   * This function takes into account the fact that a polar angles A and
   * (A + 2 * pi * k) is the same angle. Therefore the result is always in
   * a range (-pi, pi).
   * @param {Number} a
   * @param {Number} b
   * @returns {Number} Delta between a and b. The delta is such a number d that b = a + d (mod 2 pi).
   */
  function polarAngleDelta(a, b) {
    var PI2 = 2 * Math.PI;
    var d = (b - a) % PI2;
    if (d > Math.PI) {
      d -= PI2;
    } else if (d < - Math.PI) {
      d += PI2;
    }
    return d;
  }


  /**
   * Creates CanonicalRepresentation object initialized with angles and refPoints passed to constructor.
   * Note: the two arrays passed to constructor should be of the same size.
   * @param {Array<Number>} angles
   * @param {Array<Vector>} refPoints
   * @private
   * @class
   * Representation of a polygon convenient for operating with orientations of its sides.
   * This representation stores each side of the polygon as a polar angle of its normal and a reference point
   * (i.e. some point that lies on a segment).
   */
  function CanonicalRepresentation(angles, refPoints) {
    this.angles = angles.slice();
    this.refPoints = refPoints.slice();
  }


  /**
   * Converts polygon to its CanonicalRepresentation.
   * Note: the function returns null if the polygon has segments of zero length.
   * @param {Array<Vector>} polygon
   * @returns {Object}
   */
  CanonicalRepresentation.fromPolygon = function(polygon) {
    var angles = [];
    var refPoints = [];
    for (var i = 0; i < polygon.length; ++i) {
      var j = i + 1;
      if (j >= polygon.length) j -= polygon.length;
      var segment = new Segment(polygon[i], polygon[j]);
      angles.push(segment.b.minus(segment.a).ortho().angle());
      refPoints.push(segment.center());
      // Angle may be empty if the segment turned out to be of zero length.
      // This shouldn't ever happen as we've got rid of the segments of zero length.
      // If it does happen we just exit the whole function and return the original polygon.
      if (angles[i] == null) return null;
    }
    return new CanonicalRepresentation(angles, refPoints);
  }


  /**
   * Returns a normalized version of this canonical representation.
   * Normalization collapses consecutive angles in case they are equal and modifies
   * reference points accordingly (i.e. averaging them).
   * @returns {CanonicalRepresentation} Normalized CanonicalRepresentation.
   */
  CanonicalRepresentation.prototype.normalized = function() {
    // Generating a new set of angles and refPoints getting rid of equal angles
    // going in a row.
    var newAngles = [];
    var newRefPoints = [];
    var last = this.angles.length;
    var equalCount = 1;
    var refPoint = this.refPoints[0];
    var angle = this.angles[0];

    while (last > 1) {
      var delta = polarAngleDelta(angle, this.angles[last - 1]);
      if (!Precision.isZero(delta, Precision.DEFAULT.RADIAN)) {
        break;
      }
      last--;
      equalCount++;
      angle += delta / equalCount;
      refPoint = refPoint.plus(this.refPoints[last]);
    }

    pos = 1;
    while (pos < last) {
      var delta = polarAngleDelta(angle, this.angles[pos]);
      if (Precision.isZero(delta, Precision.DEFAULT.RADIAN)) {
        equalCount++;
        angle += delta / equalCount;
        refPoint = refPoint.plus(this.refPoints[pos]);
      } else {
        newAngles.push(angle);
        newRefPoints.push(refPoint.multiply(1.0 / equalCount));
        equalCount = 1;
        refPoint = this.refPoints[pos];
        angle = this.angles[pos];
      }
      pos++;
    }
    newAngles.push(angle);
    newRefPoints.push(refPoint.multiply(1.0 / equalCount));
    return new CanonicalRepresentation(newAngles, newRefPoints);
  };


  /**
   * Converts CanonicalRepresentation to an actual polygon.
   * Note: the function may return null in case there are parallel lines or the
   * resulting polygon is not valid.
   * @returns {Array<Vector>} Polygon.
   */
  CanonicalRepresentation.prototype.toPolygon = function() {
    if (this.angles.length < 3) {
      return null;
    }

    var result = [];
    prev = this.angles.length - 1;
    var prevLine = Line.fromNormalAndPoint(Vector.fromPolar(this.angles[prev], 1.0), this.refPoints[prev]);
    for (var i = 0; i < this.angles.length; ++i) {
      var curLine = Line.fromNormalAndPoint(Vector.fromPolar(this.angles[i], 1.0), this.refPoints[i]);
      result.push(prevLine.intersectLine(curLine));
      prevLine = curLine;
      if (result[i] == null) {
        // This also shouldn't happen as it means that two consequetive lines
        // turned out to be parallel (the previous part of the algorithm was
        // supposed to get rid of cases like this).
        return null;
      }
    }
    return isValidPolygon(result) ? result : null;
  };

  /**
   * Collection of static factory methods constracting different types of angle
   * correction functions to be used with correctAngles.
   * @private
   */
  var AngleCorrectionFuncFactory = {};


  /**
   * Returns angle correction function used by correctAngles.
   * The correction function being returned snaps the input angle
   * to the closest exact multiple of the snappingAngle.
   * Snapping occurs only in case the input angle is within precision.RADIAN
   * from the target angle.
   *
   * @param {Number} snappingAngle Snapping angle that will be used by the returned function.
   */
  AngleCorrectionFuncFactory.createSnappingAngle = function(snappingAngle) {
    return function(angle, precision) {
      var closestAngle = Math.round(angle / snappingAngle) * snappingAngle;
      if (Precision.equal(angle,  closestAngle, precision.RADIAN)) {
        return closestAngle;
      }
      return null;
    };
  };


  /** @exports correctAngles as geoPolygonUtils.correctAngles */
  var correctAngles =
    /**
     * <p>This function takes a polygon and corrects its angles according to correction
     * function. The most common use case is to turn angles close to being straight into
     * exact straight angles.</p>
     *
     * <p>As an angleCorrection argument you may either pass a snapping angle (e.g. when
     * you pass PI/2 the function will correct straight angles) or you can pass an angle
     * correction function. Correction function takes a delta angle (difference of angles)
     * between two consecutive segment orientations and returns 'null' if the segments
     * shouldn't be bound together (i.e. no correction should be applied) and the corrected
     * value of the delta angle otherwise (note that in most cases the corrected
     * value should be reasonably close to the original value, e.g. it shouldn't
     * be normalized in any way as it's literary a difference between two angles).
     * We need the concept of bounding the segments to each other as obviously the
     * angles should be adjusted simultaneously because they affect each other.</p>
     *
     * <p>Algorithm:
     *   <ol>
     *     <li>optimize the polygon by getting rid of the segments of zero length;</li>
     *     <li>construct an intermediate representation of the polygon as a set of
     *     normals (or rather polar angles of the normals) to its segments and
     *     the centers of the segments (note that given this information the polygon
     *     can be reconstructed in a unique way);</li>
     *     <li>we iteratively search for consequetive angles that should be corrected
     *     and apply the correction to them (we also try to minimize the cummulative
     *     effect of our adjustment by finding groups of bound angles and adjusting
     *     them all at the same time);</li>
     *     <li>reconstruct the polygon using the set of adjusted angles.</li>
     *   </ol></p>
     * @param {Array<Vector>} polygon The polygon to be corrected.
     * @param {Number|Function} angleCorrection Angle correction strategy (either a snapping angle or angle correction function).
     * @param {Precision|Number} precision Precision to be used for angle correction (in case snapping angle is used as an angle correction strategy this argument defines snapping precision).
     * @returns {Array<Vector>|null} Corrected polygon or 'null' if correction didn't succeed.
     */
    geoPolygonUtils.correctAngles = function(polygon, angleCorrection, precision) {
      var angleCorrectionFunc;
      if (typeof(angleCorrection) == 'number') {
        angleCorrectionFunc = AngleCorrectionFuncFactory.createSnappingAngle(angleCorrection);
      } else {
        angleCorrectionFunc = angleCorrection;
      }
      precision = Precision.createForRadian(precision);
      // Getting rid of segments of zero length.
      polygon = simplifyPolygon(polygon, precision) || polygon;
      if (polygon.length < 3) {
        // We can't correct angles if there aren't any.
        return null;
      }


      var canonical = CanonicalRepresentation.fromPolygon(polygon);

      var segmentLengths = [];
      for (var i = 0; i < polygon.length; ++i) {
        var j = i + 1;
        if (j >= polygon.length) j -= polygon.length;
        segmentLengths.push(polygon[i].distanceToPoint(polygon[j]));
      }

      // The number of iterations of the processing cycle below that didn't produce
      // any changes.
      var nochangeCount = 0;
      // Total number of iterations.
      var iterationsCount = 0;

      var groupStart = 0;
      var groupWeight = segmentLengths[0];
      var prev = 0;
      var pos = 1;
      while (iterationsCount < canonical.angles.length * 10) {
        if (nochangeCount > canonical.angles.length * 2) break;
        iterationsCount++;
        nochangeCount++;

        if (pos == groupStart) {
          // We shouldn't wrap the group around cyclicly.
          groupStart = prev;
          groupWeight = segmentLengths[prev];
        }

        var delta = canonical.angles[pos] - canonical.angles[prev];
        var deltaCorrected = angleCorrectionFunc(delta, precision);
        if (deltaCorrected == null) {
          groupStart = pos;
          groupWeight = segmentLengths[pos];
        } else {
          var correction = deltaCorrected - delta;
          var newGroupWeight = groupWeight + segmentLengths[pos];
          if (Math.abs(correction) > Precision.DEFAULT.RADIAN) {
            nochangeCount = 0;
            var correctionGroup = - correction * segmentLengths[pos] / newGroupWeight;
            canonical.angles[pos] += correction * groupWeight / newGroupWeight;
            var i = groupStart;
            while (i != pos) {
              canonical.angles[i] += correctionGroup;
              i++;
              if (i >= canonical.angles.length) i -= canonical.angles.length;
            }
          }
          groupWeight = newGroupWeight;
        }
        prev = pos;
        pos++;
        if (pos >= canonical.angles.length) pos -= canonical.angles.length;
      }

      return canonical.normalized().toPolygon();
    };

})();
